Turbocodes are error corrector codes, the performance of which approaches Shannon's limit as described in C. Berrou (ed.), “Codes et turbocodes” (Codes and turbocodes), “Chapitre 7: Turbocodes convolutifs” (Chapter 7: Convolutive turbocodes), IRIS Collection, Springer, 2007. The conventional structure of a turbo-encoder 1, shown in FIG. 1A, comprises the parallel concatenation of two recursive systematic convolutive codes C1 and C2 (CSR) separated by an interleaver 2. The input digital message of a length K is encoded in its order of arrival, called its natural order, by the encoder C1, and in the interleaved or permutated order by the encoder C2.
At reception, as shown in FIG. 2, the decoding of the code makes use of two soft input and output decoders or SISO (Soft-In Soft-Out) decoders. On the basis of information on the information symbols Lcys, and on the redundancy symbols Lcyr1 and Lcyr2, available at the output of the channel, each decoder computes a piece of information known as extrinsic information Le1 and Le2 on the decoded information symbols which it exchanges with the other decoder following an iterative process. The decoders thus converge towards a common decision L1.
The rate of this overall encoding R of the turbocode of FIG. 1A is equal to 1/3 (before puncturing). The technique most widely used to increase the encoding rate of a turbocode consists in puncturing the transmitted symbols with a periodic pattern. With this technique, the same encoder and the same decoder can be used for all the encoding rates. Moreover, it is accepted that it is preferable to puncture the redundancy symbols Y1 and Y2 rather than the information symbols as explained in O. Acikel and W. Ryan, “Punctured turbo-codes for BPSK/QPSK channels” IEEE Trans. Commun., vol. 47, No. 9, pp. 1315-1323, September 1999, and F. Mo et al., “Analysis of puncturing pattern for high rate turbo codes”, Proc. IEEE Conference on Military Communications (MIL-COM 1999), vol. 1, September 1999, pp. 547-550. Indeed, at reception, the information symbols are used to decode two elementary codes C1 and C2 while each redundancy is only used for the decoding of one of the codes. The absence of an information symbol is therefore in principle more penalizing than the absence of a redundancy symbol.
The puncturing of the information symbols is described in the US patent application 2008/0256424.
As shown in the article by S. Crozier et al., “On designing turbo-codes with data puncturing”, Canadian Workshop of Information Theory (CWIT 2005), June 2005, “Rate-compatible turbo codes designed with puncture-constrained DRP interleavers”, IEEE Global Telecommun. Conf., December 2011, pp. 1-5, and “On the error-rate performance of 4-state turbo codes with puncture-constrained DRP interleavers”, IEEE International Conference on Communications (ICC), June 2012, pp. 2601-2605, puncturing carefully chosen information symbols can increase the minimum Hamming distance of the turbocode and therefore improve its performance at low error rates, without in any way impairing its performance at high and medium error rates. However, to the knowledge of the Applicant, there is no method in existence relating to the manner of choosing the puncturing pattern, especially the number and positions of the punctured information symbols.
When information symbols are punctured, not all the puncturing patterns are permissible. The puncturing patterns leading to minimum Hamming distances of the elementary code equal to 0 or to 1, called catastrophic patterns, must be eliminated. Indeed, under such conditions, the elementary code loses its corrective power and, even at very low noise levels, the decoder takes wrong decisions and leads to a high error rate.
In addition, the level of reliability of the extrinsic information computed on an information symbol output from an elementary decoder depends inter alia on the position of the symbol considered in the puncturing period, the puncturing or non-puncturing of the associated redundancies and the number of punctured redundancies associated with the information symbol as the case may be. Indeed, when a single redundancy is computed by the elementary code for each information symbol, i.e. in the case of a rate RC of the non-punctured elementary code equal to 1/2 in the case of a binary code, when the redundancy is punctured, the extrinsic information computed on the corresponding information symbol is less reliable than when the redundancy is not punctured. Similarly, when several redundancies are computed by the elementary code for each information symbol, i.e. for a rate RC of the non-punctured elementary code that is lower than 1/2 in the case of a binary code, the greater the number of punctured redundancies, the lower is the reliability of the extrinsic information computed on the corresponding information symbol.
The aspect of the known error rate curve at output of a turbo-decoder is shown in FIG. 3. In the top part of the curve, with high and medium error rates, called a waterfall region, there is a region of high decrease of error rate as a function of the signal-to-noise ratio. Then, beyond a certain value of the signal-to-noise ratio, the slope of the curve diminishes indicating that the asymptotic gain of the turbocode has been attained, in a region called an error floor or error flare. The asymptotic gain of the turbocode is fixed by its distance spectrum which lists the number of words of the code at the minimum Hamming's distance and at the greater distances. The number of words of the code at the distance d is called a multiplicity associated with d.
The performance of a turbocode, especially at low error rates, in what is called the flare region, is highly dependent on the interleaving function.
The interleaver of a turbo-encoder enables efficient curbing of the occurrence of error packets at reception, at the input of at least one of the two decoders corresponding to the codes C1 and C2, playing in this way a role in the performance levels of the turbocode in the waterfall region. The interleaver also has an impact on the minimum Hamming distance of the turbocode which governs its behavior at low error rates in the flare region.
The first goal of error packet dispersal is easily obtained by means of a regular interleaver as described in C. Berrou mentioned here above, for example a row-column interleaver. However, this book shows that this type of interleaver cannot be used to obtain high minimum Hamming distances because it produces rectangular error patterns of low weight. An efficient interleaver makes it possible to break the regularity of the rectangular error patterns by introducing a degree of disorder or irregularity.
Turbocode-interleaving methods are known from the patent applications WO 2000/035103, WO 2000/010257, WO 2006/069392, US 2007/0288834, WO 2007/047472, WO 2008/057041, and WO 2010/148763.
Several families of irregular interleavers are known, especially what are called ARP (Almost Regular Permutation) interleavers, described in C. Berrou et al., “Designing good permutations for turbocodes: towards a single model,” IEEE International Conference on Communications, vol. 1, 2004, pp. 341-345, or DRP (Dithered Relative Prime), described in the article by S. Crozier and P. Guinand, “High-performance low-memory interleaver banks for turbo-codes,” IEEE 54th Vehicular Technology Conference, vol. 4, October 2001, pp. 2394-2398, or QPP (Quadratic Permutation Polynomial), described in the article by J. Sun and O. Takeshita, “Interleavers for turbo codes using permutation polynomials over integer rings,” IEEE Trans. Inf. Theory, vol. 51, No. 1, pp. 101-119, January 2005.
The ARP and DRP interleavers are based on an overall regular circular interleaving into which a certain degree of disorder is inserted through a local permutation.
The ARP interleaver described especially in the application US 2008/0086674, is based on the following mathematical model:Π(i)=(Pi+S(i mod Q))mod K, where i=0 . . . K−1 represents the address of the information symbol after interleaving and Π(i) represents the address of the same symbol before interleaving as represented in FIG. 4 in the case of circular elementary code. The parameters of this interleaver are P the period of the regular interleaver Q, a divider of K, representing the degree of disorder inserted by means of the vector S, corresponding to the adjustment vector inserting the irregularities in the regular interleaver by means of Q integer values.
The regular interleaver is expressed by: Π(i)=Pi mod K, with i=0 . . . K−1.
The DRP interleaver, considered to be a subset of ARP interleavers as explained in Garzón Bohórquez et al. “On the equivalence of interleavers for turbo codes,” IEEE Wireless Communication Letters, vol. 4, no 1, pp. 58-61, February 2015, applies a local permutation to groups of W bits before the overall regular interleaving is done, and then applies a new permutation on the groups of R bits before definitive reading.
The QPP interleaver, considered to be a particular case of the ARP interleaver as explained in the article mentioned here above by Garzón Bohórquez et al., is based on a quadratic polynomial permutation:Π(i)=(f1i+f2i2)mod K, where i=0 . . . K−1 represents the address of the information symbol after interleaving and Π(i) is the address of the same information symbol before interleaving.
The ARP interleaver has been adopted in the DVB-RCS/RCS2, DVB-RCT and WiMAX (IEEE 802.16) standards, while the QPP interleaver is used in the LTE and LTE-Advanced mobile communications standards.
Whatever the family of interleaver adopted, it is necessary to find the parameters that give the interleaver good properties of distance and therefore a flare region that is as low as possible. Ideally, since the elementary codes of the turbocode are fixed, the values of these parameters must be computed for each size K of the block of the message to be encoded and for each encoding rate value.
However, the process of searching for these parameters proves in practice to be cumbersome and consumes computation power, because for each set of parameters considered, it is necessary either to simulate the behavior of the turbocode at low error rates in order to detect the position of the flare region or to estimate its distance spectrum by means of methods such as those described in C. Berrou et al., “Computing the minimum distance of linear codes by the error impulse method,” IEEE Global Telecommun. Conf., vol. 2, November 2002, pp. 1017-1020, or by R. Garello and A. Vila-Casado, “The all-zero iterative decoding algorithm for turbo code minimum distance computation,” IEEE International Conference on Communications (ICC), vol. 1, June 2004, pp. 361-364, or the articles by S. Crozier et al. “Estimating the minimum distance of turbo-codes using double and triple impulse methods”, IEEE Commun. Lett., vol. 9, No. 7, pp. 631-633, 2005, or “Estimating the minimum distance of large-block turbo codes using iterative multiple-impulse methods,” 4th Int. Symposium on Turbo Codes and Related Topics (ISTC), 2006, pp. 1-6, or “Estimating the minimum distance of large block turbo codes using the event impulse method” Int. Symposium on Turbo Codes and Iterative Information Processing (ISTC), September 2010, pp. 439-443.
Thus, in practice, in the standards using ARP and QPP interleavers, for each block size K, the interleaving parameters do not depend on the encoding rate and the turbocodes obtained do not have high performance in terms of correction for all the coding rate values, especially for the high rate values.
Given the present limitations of turbocodes, described here above, there is a need to improve the performance of information symbols encoding that implement a turbo-encoder.